#ifndef __LEETCODE_H__
#define __LEETCODE_H__

#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/* ————————————  官方 - leetcode  ———————————————————— */
/**
 * Definition for singly-linked list.
 */
struct ListNode {
	int val;
	struct ListNode* next;
};

/* ————————————  官方 辅助 - leetcode  ———————————————————— */
size_t ListNode_len(struct ListNode* node)
{
	size_t len = 0;
	while (node) {
		len++;
		node = node->next;
	}
	return len;
}

/* ————————————  默认参数  ———————————————————— */
#define DEFAULT_CAPACITY 16

/* ————————————  动态数组 ———————————————————— */
typedef struct {
	ElemType* _data;
	size_t _size;	// 当前含量
	size_t _length; // 最大容量
} vector;

/**
 * 初始化 动态数组
 * @param 初始化容量
 * @return 其在内存中的首地址
 */
vector* vector_initn(int capacity)
{
	vector* vec = malloc(sizeof(vector));
	vec->_data = calloc(capacity, sizeof(ElemType));
	vec->_size = 0;
	vec->_length = capacity;

	return vec;
}

/**
 * 初始化 动态数组 (默认容量)
 * @return 其在内存中的首地址
 */
vector* vector_init()
{
	return vector_initn(DEFAULT_CAPACITY);
}

/**
 * 向 动态数组 中插入元素
 

*/
void vector_insert(vector* vec, size_t index, ElemType elem)
{
	/* 内存是否足够？*/
	if (vec->_size + 1 == vec->_length) {
		size_t new_len = vec->_length * 1.5;
		vec->_data = realloc(vec->_data, new_len * sizeof(ElemType));
		vec->_length = new_len;
	}

	ElemType* arr = vec->_data;
	for (int i = vec->_size; i > index; i--)
		arr[i] = arr[i - 1];

	arr[index] = elem;
	vec->_size++;
}

/**
 * 在 动态数组 中根据 下标 删除一个元素
 * @return ElemType 被删除元素的值
 */
ElemType vector_delete(vector* vec, size_t index)
{
	ElemType* arr = vec->_data;
	ElemType e = arr[index];

	for (int i = index, len = vec->_size; i < len; i++)
		arr[i - 1] = arr[i];
	vec->_size--;

	/* 元素太少时, 缩减空间 */
	if (vec->_size > 8 && vec->_size == vec->_length / 2) {
		size_t new_len = vec->_length / 5 * 3;
		vec->_data = realloc(vec->_data, new_len * sizeof(ElemType));
		vec->_length = new_len;
	}

	return e;
}
/* ————————————   ———————————————————— */

#endif
